package io.github.handyang.algorithms.sort;

import java.util.Arrays;

public class LSDRadixSortAlgorithms implements SortAlgorithms {
    @Override
    public void sort(int[] arr) {
        int maxLen = maxLen(arr);

        int[] temp = new int[arr.length];
        int[] count = new int[11];
        int radix = 1;
        for (int i = 0; i < maxLen; i++) {
            for (int item : arr) {
                //count 是基数为 i 的最后一个索引
                count[(item / radix) % 10 + 1]++;
            }

            //转化为索引
            for (int j = 1; j < count.length; j++) {
                count[j] += count[j - 1];
            }

            for (int item : arr) {
                temp[count[(item / radix) % 10]++] = item;
            }

            System.arraycopy(temp, 0, arr, 0, temp.length);
            Arrays.fill(count, 0);
            radix *= 10;
        }
    }

    private int maxLen(int[] arr) {
        int max = arr[0];
        for (int item : arr) {
            if (item > max) max = item;
        }

        int i = 1;
        while (max >= 10) {
            i++;
            max /= 10;
        }

        return i;
    }
}
